import java.util.Stack;

public class towork1 {

 //找最近祖先   方法二通过stack去找到p q的路径
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        getpath(root,p,stack1);//获取stack的路径
        getpath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        if(size1>size2){
            int size=size1-size2;
            while(size!=0){
                size--;
                stack1.pop();
            }
        }
        else{
            int size=size2-size1;
            while(size!=0){
                size--;
                stack2.pop();
            }
        }
        while(!stack1.isEmpty()&&!stack2.isEmpty()){
            TreeNode val1= stack1.pop();
            TreeNode val2= stack2.pop();
            if(val1==val2){
                return val1;
            }
        }
        return null;
    }
    public boolean getpath(TreeNode root ,TreeNode Node,Stack<TreeNode> stack ){
        if(root==null){
            return false;
        }
        stack.push(root);
        if(root==Node){
            return true;
        }
        boolean flag=getpath(root.left,Node,stack);
        if(flag==true){
            return true;
        }
        boolean fla=getpath(root.right,Node,stack);
        if(fla==true){
            return true;
        }
        stack.pop();
        return false;
    }
}
